#include <bits/stdc++.h>
using namespace std;

/*
2966. 划分数组并满足最大差限制
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。

将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：

子数组中 任意 两个元素的差必须 小于或等于 k 。
返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。

 

示例 1：

输入：nums = [1,3,4,8,7,9,3,5,1], k = 2

输出：[[1,1,3],[3,4,5],[7,8,9]]

解释：

每个数组中任何两个元素之间的差小于或等于 2。

示例 2：

输入：nums = [2,4,2,2,5,2], k = 2

输出：[]

解释：

将 nums 划分为 2 个长度为 3 的数组的不同方式有：

[[2,2,2],[2,4,5]] （及其排列）
[[2,2,4],[2,2,5]] （及其排列）
因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。

示例 3：

输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14

输出：[[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]

解释：

每个数组中任何两个元素之间的差小于或等于 14。

 

提示：

n == nums.length
1 <= n <= 105
n 是 3 的倍数
1 <= nums[i] <= 105
1 <= k <= 105
*/

// 法一
// 数组划分 分组检查​​：
class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();

        // 检查 是否是3 的倍数
        if (n % 3 != 0)         return {};
        for(int i = 0; i < n; i += 3) {
            // 当前三个连续元素的差值
            if (nums[i + 2] - nums[i] > k)  return {};
            // 满足条件的子数组push进ans
            ans.push_back({nums[i], nums[i + 1], nums[i + 2]});
        }
        return ans;
    }
};

// 法二
// 双指针
class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();

        // 检查 是否是3 的倍数
        if (n % 3 != 0)         return {};
        // 双指针
        // 差异就在此处 找子数组的区别
        int left = 0;
        while (left < n) {
            int right = left + 2;
            // 越界检查
            if (right >= n)     return {};
            if (nums[right] - nums[left] > k)   return {};

            ans.push_back({nums[left], nums[left + 1], nums[right]});

            // 左指针位置更新 指针滑动
            left += 3;
        }
        return ans;
    }
};

// 具体思路解析
class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        // 1. 首先对数组进行排序，这样相邻元素的差值最小化
        // 排序后更容易找到满足条件的子数组
        sort(nums.begin(), nums.end());
        
        // 2. 初始化结果容器，用于存储满足条件的子数组
        vector<vector<int>> ans;
        
        // 3. 遍历数组，每次处理3个连续元素
        // 从索引2开始，每次步进3，这样i-2,i-1,i就是连续的三个元素
        for (int i = 2; i < nums.size(); i += 3) {
            // 4. 检查当前三个元素的最大差值是否超过k
            // 因为数组已排序，nums[i]是当前三个元素的最大值
            // nums[i-2]是当前三个元素的最小值
            // 它们的差值代表当前子数组的最大差值
            if (nums[i] - nums[i - 2] > k) {
                // 5. 如果任何一组不满足条件，立即返回空数组
                return {};
            }
            
            // 6. 将满足条件的子数组加入结果集
            // 使用花括号初始化语法创建包含三个元素的子数组
            ans.push_back({nums[i - 2], nums[i - 1], nums[i]});
        }
        
        // 7. 如果所有子数组都满足条件，返回结果
        return ans;
    }
};